package com.wp.targetOffer;

import java.util.Arrays;

/**
 * Created by 王萍 on 2017/8/1 0001.
 */

/**
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
 * 所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 * 注意：reOrderArray2方法的实现比较难以理解。但是不需要辅助内存。
 */
public class 调整数组顺序使奇数位于偶数前面 {

    public static void main(String[] args) {

        int[] array = {1, 2, 3, 4, 5, 6, 7};
        Arrays.stream(reOrderArray2(array)).forEach(x -> System.out.print(x + " "));
    }

    /**
     * 先求出奇数的个数，然后新建一个大小一样的数组，再遍历原数组判断奇偶填充到新数组中。
     * 牛客网上未通过。
     */
    public static int[] reOrderArray(int[] array) {
        int ji = 0, ou;
        int[] result = new int[array.length];
        for (int a : array) {
            if (a % 2 == 1) ji++;
        }
        ou = ji;
        ji = 0;
        for (int a : array) {
            if (a % 2 == 0) result[ou++] = a;
            else result[ji++] = a;
        }
        return result;
    }

    public static int[] reOrderArray2(int[] a) {

        if (a == null || a.length == 0)
            return null;
        int i = 0, j;
        while (i < a.length) {
            while (i < a.length && !isEven(a[i]))
                i++;
            j = i + 1;
            while (j < a.length && isEven(a[j]))
                j++;
            if (j < a.length) {
                int tmp = a[j];
                for (int j2 = j - 1; j2 >= i; j2--) {
                    a[j2 + 1] = a[j2];
                }
                a[i++] = tmp;
            } else {// 查找失敗
                break;
            }
        }
        return  a;
    }

    //是偶数
    public static boolean isEven(int n) {
        if ((n & 1) == 0)
            return true;
        return false;
    }
}
